#include "RegextoNFA.h"

miniDFA nfaToDFA(const RegextoNFA& nfa) {
    map<set<State*, StatePtrCompare>, State*, SetComparator> dfaStatesMap; // 用于映射NFA状态集合到DFA状态的映射表
    queue<set<State*, StatePtrCompare>> nfaStatesQueue; // 用于BFS遍历的集合队列
    set<State*, StatePtrCompare> dfaStates;
    set<State*, StatePtrCompare> dfaEndStates;

    set<State*, StatePtrCompare> nfaStartClosure = epsilonClosure({ nfa.startState });
    State* dfaStartState = new State(0);
    dfaStatesMap[nfaStartClosure] = dfaStartState;
    dfaStates.insert(dfaStartState);
    nfaStatesQueue.push(nfaStartClosure);

    int nextStateId = 1;
    //set<State*, StatePtrCompare> nfaStartClosure
    while (!nfaStatesQueue.empty()) {
        set<State*, StatePtrCompare> currentNFAStates = nfaStatesQueue.front();
        nfaStatesQueue.pop();
        State* currentDFAState = dfaStatesMap[currentNFAStates];

        // 检查是否有终止状态，如果有，设置DFA状态为终止状态
        for (State* nfaState : currentNFAStates) {
            if (nfaState->isFinalState) {
                // cout << nfaState->id << "is FinalState" << endl;
                currentDFAState->setFinalState(true, nfaState->wordType);
                dfaEndStates.insert(currentDFAState);
                break;
            }
        }

        // 遍历所有输入字符类型
        for (int i = 0; i < static_cast<int>(EPSILON); i++) {
            InputCharType inputCharType = static_cast<InputCharType>(i);
            set<State*, StatePtrCompare> nextNFAStates = epsilonClosure(move(currentNFAStates, inputCharType));
            if (nextNFAStates.empty()) {
                continue;
            }

            // 如果NFA状态集合不存在于映射表中，则创建新的DFA状态
            if (dfaStatesMap.find(nextNFAStates) == dfaStatesMap.end()) {
                State* newDFAState = new State(nextStateId++);
                dfaStatesMap[nextNFAStates] = newDFAState;
                dfaStates.insert(newDFAState);
                nfaStatesQueue.push(nextNFAStates);
            }
            currentDFAState->addTransition(inputCharType, dfaStatesMap[nextNFAStates]);
        }
    }

    return miniDFA(dfaStartState, dfaEndStates, dfaStates);
}

set<State*, StatePtrCompare> move(const set<State*, StatePtrCompare>& states, InputCharType input) {
    set<State*, StatePtrCompare> targetStates;
    for (State* state : states) {
        auto it = state->transitions.find(input);
        if (it != state->transitions.end()) {
            for (State* targetState : it->second) {
                if (targetStates.find(targetState) == targetStates.end()) {
                    targetStates.insert(targetState);
                }
            }
        }
    }
    return targetStates;
}

set<State*, StatePtrCompare> epsilonClosure(const set<State*, StatePtrCompare>& states) {
    set<State*, StatePtrCompare> closure = states;
    stack<State*> stateStack;
    for (State* state : states) {
        stateStack.push(state);
    }
    while (!stateStack.empty()) {
        State* currentState = stateStack.top();
        stateStack.pop();
        auto it = currentState->transitions.find(EPSILON);
        if (it != currentState->transitions.end()) {
            for (State* nextState : it->second) {
                if (closure.find(nextState) == closure.end()) {//防止同一状态多次进栈，set自带去重
                    closure.insert(nextState);
                    stateStack.push(nextState);
                }
            }
        }
    }
    return closure;
}

void printDFA(const miniDFA& dfa) {
    cout << "Start state: " << dfa.startState->id << endl;
    cout << "End states: " << endl;
    for (auto state : dfa.endStates) {
        cout << state->id << " " << getWordTypeName(state->wordType,"") << endl;
    }
    cout << endl;
    cout << "States and transitions:" << endl;
    for (auto state : dfa.states) {
        cout << "State " << state->id << ":" << endl;
        for (auto transition : state->transitions) {
            cout << "\tInput " << getInputChartypeName(transition.first) << ": ";
            for (auto targetState : transition.second) {
                cout << targetState->id << " ";
            }
            cout << endl;
        }
    }
}
